package threeSum

import "sort"

/**
三数之和
定义三个指针left，mid，right
for left从0开始向右移动，直到len(nums)-2，
	for mid从left +1开始向右移动，right从len(nums)-1开始向左移动
*/
func threeSum(nums []int) [][]int {
	if len(nums) < 3 {
		return [][]int{{}}
	}
	sort.Ints(nums)
	left := 0
	ans := [][]int{}
	for left < len(nums)-2 {
		target := 0 - nums[left]
		start := nums[left]
		mid, right := left+1, len(nums)-1
		for mid < right {
			sum := []int{}
			result := nums[mid] + nums[right]
			l, r := nums[mid], nums[right]
			if result < target {
				// 跳过相同的
				for mid < right && nums[mid] == l {
					mid++
				}
			} else if result > target {
				// 跳过相同的
				for mid < right && nums[right] == r {
					right--
				}
			} else {
				sum = append(sum, nums[left], l, r)
				// 跳过相同的
				for mid < right && nums[mid] == l {
					mid++
				}
				// 跳过相同的
				for mid < right && nums[right] == r {
					right--
				}
				// 找到了，加入切片
				ans = append(ans, sum)
			}
		}
		// 跳过相同的
		for left < len(nums)-2 && nums[left] == start {
			left++
		}
	}
	return ans
}
